package com.leetcode.midium;

import java.util.HashSet;
import java.util.Set;

/**
 * @author zfl
 * @Classname LengthOfLongestSubstring
 * @Description 无重复字符的最长子串
 * @Date 2020/10/7 16:38
 */
public class LengthOfLongestSubstring {

    /**
     * @param s
     * @return
     * 滑动窗口
     * 执行用时：8 ms, 在所有 Java 提交中击败了69.66%的用户
     * 内存消耗：39.1 MB, 在所有 Java 提交中击败了53.10%的用户
     * for循环中i++和++i:
     * 1、++i是先改变i的值即加1后再使用i的值；而i++是先使用i的值在改变它的值即加。
     * 2、for循环内部仅形式不同：当i++循环和++i循环在for循环内部，虽然形式上明显不同，但输出结果可以一样。
     */
    public static int lengthOfLongestSubstring(String s) {
        // 哈希集合，记录每个字符是否出现过
        Set<Character> occ = new HashSet<>();
        int n = s.length();
        // 右指针，初始值为-1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        for(int i = 0; i < n; ++i) {
             if(i != 0) {
                 // 左指针向右移动一格，移除一个字符
                 occ.remove(s.charAt(i - 1));
             }
             while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) {
                 occ.add(s.charAt(rk + 1));
                 ++rk;
             }
             // 第i到rk个字符是一个极长的无重复字符子串
            ans = Math.max(ans,rk - i + 1);
        }
        return ans;
    }
}
